#include<iostream>
#include<vector>
using namespace std;
/*
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些
（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
解题思路：
该题目与求最长公共子序列的题目类似,我们要求出两个字符串的最长公共子序列然后判断最长公共子序列的长度是否等于s字符串的长度
所以有dp[i][j]表示s中下标为i-1和t中下标为j-1的最长公共子序列的长度
if(s[i-1]==t[j-1])
    dp[i][j] = dp[i-1][j-1]+1
else 
    dp[i][j] = dp[i][j-1]
这里与最长公共子序列的递推公式略有差别是因为只有t才能被删除元素进行判断
*/
bool dp(string s,string t)
{
    //创建dp数组并进行初始化
    vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1));
    int result=0;
    for(int i=1;i<=s.size();i++)
    {
        for(int j=1;j<=t.size();j++)
        {
            if(s[i-1]==t[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = dp[i][j-1];
            if(dp[i][j]>result)
                result = dp[i][j];
        }
    }
    cout<<result<<endl;
    if(result==s.size())
        return true;
    return false;
}
int main()
{
    string s,t;
    cout<<"enter s:"<<endl;
    cin>>s;
    cout<<"enter t:"<<endl;
    cin>>t;
    cout<<dp(s,t);
    return 0;
}